﻿#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;



/*
给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。

你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。
在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。

一条路径的 「得分」 定义为：路径上所有数字的和。

请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，
请把结果对 10^9 + 7 取余。
如果没有任何路径可以到达终点，请返回 [0, 0] 。


示例 1：
输入：board = ["E23","2X2","12S"]
输出：[7,1]

示例 2：
输入：board = ["E12","1X1","21S"]
输出：[4,2]

示例 3：
输入：board = ["E11","XXX","11S"]
输出：[0,0]
 

提示：
2 <= board.length == board[i].length <= 100

*/




//sample
class Solution {
public:
	vector<int> pathsWithMaxScore(vector<string>& board) {
		int n = board.size();
		vector<vector<int>> f(n, vector<int>(n, -1));
		vector<vector<int>> g(n, vector<int>(n, 0));

		const int dx[3] = { 0, -1, -1 };
		const int dy[3] = { -1, -1, 0 };
		const int mod = 1000000007;

		board[n - 1][n - 1] = '0';
		f[0][0] = 0;
		g[0][0] = 1;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 'X')
					continue;
				for (int k = 0; k < 3; k++) {
					int x = i + dx[k], y = j + dy[k];
					if (x < 0 || y < 0 || f[x][y] < 0)
						continue;

					if (f[i][j] < f[x][y] + board[i][j] - '0') {
						f[i][j] = f[x][y] + board[i][j] - '0';
						g[i][j] = g[x][y];
					}
					else if (f[i][j] == f[x][y] + board[i][j] - '0') {
						g[i][j] = (g[i][j] + g[x][y]) % mod;
					}
				}
			}

		if (f[n - 1][n - 1] < 0)
			return { 0, 0 };
		return { f[n - 1][n - 1], g[n - 1][n - 1] };
	}
};

 

//class Solution {
//public:
//	vector<vector<vector<int>>> path;
//	const int MOD = 1e9 + 7;
//	int pathFunc(vector<string>& board, int x, int y, int score) {
//		int m = board.size(); int n = board[0].size();
//		if (x < 0 || x >= m || y < 0 || y >= n || score<0) return 0;
//		
//		int& v = path[x][y][score];
//		if (v != -1) return v;
//		v = 0;
//
//		if (board[x][y] == 'X') { v = 0; return v; }
//		if (board[x][y] != 'E' && board[x][y] != 'S') {
//			score -= board[x][y] - '0';
//			if (score < 0) {
//				v = 0; return v;
//			}
//		}
//
//		if (x + 1 < m) {
//			v += pathFunc(board, x + 1, y, score);
//			v %= MOD;
//		}
//		if (y + 1 < n) {
//			v += pathFunc(board, x , y + 1, score);
//			v %= MOD;
//		}
//		if (x + 1 < m && y + 1 < n) {
//			v += pathFunc(board, x+1, y + 1, score);
//			v %= MOD;
//		}
//
//		return v;
//	}
//
//	vector<int> pathsWithMaxScore(vector<string>& board) {
//		int m = board.size(); int n = board[0].size();
//		vector<vector<int>> dp(m,vector<int>(n, -99999999));
//		
//		dp[0][0] = 0;
//		for (int x = 0; x < m; x++) {
//			for (int y = 0; y < n; y++) {
//				int val = 0;
//				if ( board[x][y] == 'X'|| board[x][y] == 'E') {continue; }
//				if ( board[x][y] != 'S') {
//					val += board[x][y] - '0';
//				}
//				if (x > 0) {
//					dp[x][y] = max(dp[x][y], dp[x - 1][y]+val);
//				}
//				if (y > 0) {
//					dp[x][y] = max(dp[x][y], dp[x][y - 1]+val);
//				}
//				if (x > 0 && y > 0) {
//					dp[x][y] = max(dp[x][y], dp[x-1][y - 1]+val);
//				}
//			}
//		}
//
//		if (dp[m - 1][n - 1] < 0)  dp[m - 1][n - 1] = 0;
//		//cout << "dp = " << dp[m - 1][n - 1] << endl;
//		int maxScore = dp[m - 1][n - 1];
//		//======================================================================================
//		path.resize(m,vector<vector<int>>(n,vector<int>(maxScore+10,-1)));
//		path[m-1][n-1][0] = 1;
//		for (int i = 1; i <= maxScore; i++) {
//			path[m - 1][n - 1][i] = 0;
//		}
//		int ans = pathFunc(board,0,0, maxScore);
//		//cout << "ans = " << ans << endl;
//
//		return vector<int>{maxScore, ans};
//	}
//};



//
//int main() {
//	Solution s;
//
//	vector<string> v = { 
//		"E9569146123X375952581X64X49XX831872392541174366698929691568X58393956432X9396671123912655895939786191",
//		"74638375176537321452533851XX8542188423789455397277796674X865X84861765919455173X869767924865735345829",
//		"33513722655948763X89X7739985955988425X28579X769273996182X6798169XX99536133X35X53X2638378429646964956",
//		"6438236753873722839X74276546434273XX2211863X927667538X242116813816315124442X42442XX5XX1X3955X6X6X421",
//		"437518328438753391485348172592854272621322693129735852X74X6924968889X4675319428924971478212214137791",
//		"11385146X7513543794544X457X6644X87439X9X34839482X764X9X5818671X785366941X547449127717158473747833443",
//		"45641123X4X5754561479745853X66771795969X778596153X79212794471677966X86253X93228515X753X73849X2785598",
//		"2522727258X765476962X4928X24812744455X415X3268656X7287394X88X48X7X855393938434988547X732378724493385",
//		"188471499745576416288761364325751518284848X58666938168XX4897395X6X5328881959652332193X364332148X3542",
//		"366548X19X642879516X79X55889922353193196XX9655365645X91778573345851567211982881813687X6325X524354XX1",
//		"96132472X71226X1X868538X18X14X6938331556137463167584464X5579469X48885X48184557925512X1118138791XX732",
//		"9X3719866158778274XX15158748588X76413489811X72916114449315843362584X545573899245585173437385585XX813",
//		"2X3514483749X221963X2645495675232562X71X134466X88482X85248X38218689X37X8147XXX9X955X952986276X8XX1X5",
//		"582266224X61351525691782257225X3286923982X79146269X238117728416419725538X19554X928311448294433511X86",
//		"4655362187974361262758728527569597X152216X5538XX5657364166X376129X2954116933456115874X43541X8X6X5X66",
//		"1XX3XX2491956156644953129193586126571X16221353589499884482144584379214618858939X317937X3X371X8838268",
//		"244373X435X238X31X16754X18XX3368896X959XXX7XX536583X714X718X42186163638X2184X16985357426X1966X7X5174",
//		"27179348562X137826321X6677637528X86163XX5X4113956434486657X3X38X5X927925616671321197647566629268X677",
//		"3X27X2X5928928818853776593922686X426XX14687614198258X2192693629259X611839416X22X6462481375882X45X439",
//		"62828X7455X75X155778513368651357X88695X2X543461616165X86X492X3192X3742743589861691649214X28729514373",
//		"5373587735685X7838XXX87425189X46646X27393X415823632781373687686962682211796275X657649X366X884277492X",
//		"53313X136X347X3X748X624863628X6123571541386278762X617X5X496419458369X943346XX2657228536346988224915X",
//		"87X97288936598X555X53627844735648922343636X5X17X194447929339X4848375433958588289799825342646272X796X",
//		"2788X66329993961821X941X112912337675912824684X41X2997X8779X2795654141125686X6523419524676224X1747259",
//		"954X5773814221785X74755219X1952997823966727263953642XX6X49446716679258148234878417742X7X676333775874",
//		"469877625X4191565838329292478119655619X955X3337X4588669751248XX3595476414662817326167461511257747816",
//		"822644262299X74476XX326593873724X8192245X31X8X68426788976X2426X4862X3879911691428256X9438491X9948822",
//		"5294587811988214X4323583824343586333856413893XX36457X555561744X298427696616823327371597263846958461X",
//		"7X9646XX47252478X228928X81X353593476623126136679X77219617423X62141X7134335748528856596X7715565643462",
//		"X8386896884622158645491454892X279315876458918552248357678452X89282455728841X883X956467XX68X1X1695978",
//		"62234433281679599724X9XX31915781677299116831182X2XX4922689869X19X49282938359777439262235349X84218X28",
//		"669732877479428832XX736871567X6X44981X4425997782865X6597X8564496659998184368611567157941563295X1X344",
//		"88837X8738735X4436X241842793955196653X96655759489X384335662328X829725136838X6634372391X9987747268951",
//		"245163634564873515199X22633261752659895422172X9216227X4131X152215X14271518X8163942344454932X2939154X",
//		"6232X4268534211432797X7322124X5976X78928X219429989X66749816212X181448393781548335135X42588718843XX63",
//		"2886396X26961414221937994X15386X2393196XX2X45866X9462929977539319832785386X756277787674X6X2831682576",
//		"8287976X8992394132852X7993257XXX474721X483X83X457783644191X91366X9496838X3185X8364XX3326159555444913",
//		"6353861864313643949137X81X1315X586162541X41198487436769949446XX8XX6794238X18951364996375785235335579",
//		"232538665783X421X763X82661X1679842138283212455254272X1239639426236776539179434X38354789495951284296X",
//		"98195566264191X2411316114296863879736376279667229773X586722672232168786325X8795X53X368616232X62275X8",
//		"4579XX578864429545274X19675417698283X9X8361X71XX54587394667X5199151497852387X85884953523917129348455",
//		"396XX48541977639595X955423281122XX6837394X1X638X6734649754456542X36416842555593582683236X76345X14995",
//		"891586836341793938565986634X638X64X95972X5728713932149X412466118X24152423X84178841342692513643659843",
//		"86993X299X3159X23637139326X4396X4X996492916273598X5551337233369959339575X876626X24487917333X5X152871",
//		"19517489576945X8149X7927417X7X31664627362958677297167XX78X52X62373728938X651X7958X439375415292X79995",
//		"9XX418329377X7X455174X69X5411X86744178867232X93733165X78X2293159275255652XX73133X58246753X721X534X97",
//		"X55414X767XX6865XX898496878X218866539X373978789X69963464193X867X943624311545X299359416286X671873119X",
//		"X7635X84X1X18X33275582355X98121126793456665661625X6X177X68531239538267239677119119272X63866711849833",
//		"68676445X26861X18145X8514678126817775525X685XX251X3961674454546484224712313711854X28X89134578547X828",
//		"4698781737447597X1X39XX4552614547X15855XX69841537951243552876129288X78678557248481295548X93841769296",
//		"725X21X32788575537X216672225X18844417556639369192315699614718452276X141211756138365962472X4817535298",
//		"754369X3266299636813659961656398X655646964X51188292X99295X9956629862628X432X3163X2X14186218333X57636",
//		"239137915476918259X6X1783773325488563195X64139373X29538X8247283324781376487X88567715594884X136893X57",
//		"3125933474X8712X216X28619347546571313972432148X141X977427X152713841116X47522139251314543679677X125X4",
//		"853361912839162X5236626443X3X8397X627562341866X8472618395797X2457X4551X46868572527214519X288X8413688",
//		"957X427866581X19659382648214X2472X1XX381939598618X879755736X5212642377854115X463611X3696178121216966",
//		"438942291114X215481963594X35859X73656X96997369336X69891X49X2878766316696252755X81532X6X7654946699X44",
//		"59X324561928X7676284139813359168415971851442X4X9565378111622452985692489X17369264922176893X859227363",
//		"6742897915927181937786X834786551366583237474693176912742127X53X552X769332321X743836689X5137557762262",
//		"X398644144X97859877157112242X898478XX52182X14X46846X253132688442476163X2178348465X583923X69843158841",
//		"32987324XX2455X349628X92525X44768478475183X13786792X773983362688XX139565X9187546756833X6284153871563",
//		"74254115X4X1278XX63XX15611216326955393X93X58572496279478322X22993864795587135724748144X59851X4563448",
//		"2436391198236325846723452347X8623273X8X6988511XX4X44935581351417679621427527572268XX6531429555924X64",
//		"52226X41512918X549X3928696X5121X93936595X79731887X9497818126X588349338782X16263X1X122623778897578617",
//		"45945968574473185X12852X628XX72425137992772X6124X146X637X5486X6X87428X31463661819954XX916254X5899298",
//		"7592X6X695724961387X36951936286X8931159928927X15253156778289948X3489561X12X39636546527X9811819717593",
//		"1482993897864X28583338134164723X64175352X9385X7939X49973393821X8718995X54X3272681112241761X61931X12X",
//		"529859649818383482388X378X96648562838747X8628992528X92322352156843189195391411X76677489731X725789513",
//		"2463X683486X6214739866X882579531X89162165421X379568X457422281295338338653261226446X835814X847X23X336",
//		"1191364154157114712X5963463154575598241X814X416X2199921187248912869224588X7XX4573X69X211763XX8625583",
//		"79977596X9X36X53726X93456632611628826514594XX7X7419262192X68939X46X837893817X82446174359195527873753",
//		"49388193749293121X3X6128X2826XX8115875X894848X3284793X6833689431625635944663X18481X625X5797896X54121",
//		"XX3431623X1959621457588X24X739973X759978214X4292841X6542325661994295429762X71253432621351345728X4783",
//		"967257847542942X1X4233X3744X3X4434236987677154386796497214564761X5X4863XX515X69X42X366X479253X998597",
//		"777989697314X76565X3XX23743871XX97545X261X75X83X537288388123671416595X161131X65X1843X876242656879454",
//		"47628668656X42158X792649458571177X418259X356X1455758X7263529X295222X854486137429391344927X9749389163",
//		"186X82567X8X775363X723X57X62835134172444481878142281822127X281179495X3X95188945217533552248993119543",
//		"1565X7562X7396767942656X176317259612688268852591222X39X92641697X654167236348858993754688271354956653",
//		"X81394722735746957XX1X468837323868X42XX96956513355X784166731891459371X3476537536292486186X628115X332",
//		"59534321816X888X43X14949746X667217365635X155X532414952584738436958492X3635589322337XX9878X6793894491",
//		"9844X11139987X8911431738571738938756655451873289494526349556X26X65236437323859272488XXX8X68842857441",
//		"1X14X433881129XX53X1378991X886X728524378X95XX25X61X851134958825851X415847X53144133784926X93X27789X6X",
//		"696895352311X97X8X39X3X64379X1546676646828571849531381547121X272676736836725176X4678X535148687594432",
//		"5521735365598711X6XX43211254758576485974X2341419X89147941686711141X4342X6218723366776636267472X55192",
//		"3287118327492974612212X941243931846929138294X73X6761568596X6X7132189367759327895399X25X4983796727451",
//		"6324495927678341738X1393X586X68899X5141153528639X22X85X719145X948XX7736X819982468185XX9X6X9157946295",
//		"19438285447863145985895X9859662X6939958X331999955X519767954812435892124147494X91564314X95X2X19XX7712",
//		"255545714717X1168X55571857391851586554499827661858153419X856953963X655X9X23X8491266X787932X27188X789",
//		"291354X942136556875968529369X393631X47253319X3127X31X7836541179533X57293896492967129994X3963X2358935",
//		"985187313X7698467773X336X1327737X2828X567521864114X8291154629388114597583438X7X46X635X827973X9839417",
//		"724X39861772X231476117X47996497745XX262315X58263134353XX5465622564X6252265696XX74671X88548X614X69852",
//		"4X854437119X7416XX98267473819815XX72X825581X95421X2845X883477251336474913X8591275662X881164887X77353",
//		"571213213X268462X7286581X76788X8X947318167493549724784959776X82268787339297254226734211467987X347822",
//		"94274858531776X12122734X1254X4118664283791797X26786X55X7559317X24511115X282X952192928551777256484992",
//		"281616972X88X63X51X865297X872891719434473113312151X5X4X6X99331953X7448245189921297X742231561964953X9",
//		"1882X1392654X761143161214846X7X4968468258224277X34478X1X42X258XX3113619739533748788916149X63X3399726",
//		"XX9459895425312959X7553437X123351X846828355841214779X19699912829256159X6446887X3X281784X88986X9X1X42",
//		"X899287712963933X15611X64694845X62X65188X1989951596538294X384X178525887865835X3953585346437341968976",
//		"417X943X8X97928269X6792982587X485619552628274268987596X2314XX873X63432X875114964X842834374X245522358",
//		"62X23921X3216869XX42476981X95696X44749351885692X1X42727X2X375858X18199X162477151X68X164471X9633898XS" };
//
//	s.pathsWithMaxScore(v);
//
//
//	return 0;
//}